package 中等.脑筋急转弯;

/**
 * 有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，
 * 其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，
 * 而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。
 * 在一步操作中，你可以将 一个 小球从某个盒子移动到一
 * 个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需
 * 满足 abs(i - j) == 1 。注意，操作执行后，某些盒子
 * 中可能会存在不止一个小球。
 * 返回一个长度为 n 的数组 answer ，其中 answer[i] 是
 * 将所有小球移动到第 i 个盒子所需的 最小 操作数。
 * 每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box
 */
public class 移动所有球到每个盒子所需的最小操作数_1769 {

    public static void main(String[] args) {

        minOperations2("110");

    }

    /**
     * 模拟
     *
     * @param boxes
     * @return
     */
    public int[] minOperations(String boxes) {
        char[] boxArr = boxes.toCharArray();
        int[] ans = new int[boxes.length()];

        for (int i = 0; i < ans.length; i++) {
            int sum = 0;
            for (int j = 0; j < ans.length; j++) {
                if (boxArr[j] == '1') {
                    sum += Math.abs(i - j);
                }
            }
            ans[i] = sum;
        }
        return ans;
    }

    /**
     * 计算出一个初始值，i 的操作数为 operate[i]，i 左边的小球数量为 left
     * i 右边的小球数量为 right，那么 operate[i+1] 的操作数可以由 left
     * 个小球全部向右移动一位，操作数 + left，right 个小球全部向右移动
     * 一位，操作数 -right
     * 得到
     * operate[i+1] = operate[i] + left - right
     * 遍历过程中需要维护 left 和 right 的数量
     *
     * @param boxes
     * @return
     */
    public static int[] minOperations2(String boxes) {
        char[] boxArr = boxes.toCharArray();
        int[] operate = new int[boxes.length()];
        // 注意：下面是从 operate[1] 算起的，如果 boxArr[1] 那么 idx = 1 的左边有 1个小球
        int left = boxArr[0] - '0', right = 0;
        for (int i = 1; i < boxArr.length; i++) {
            if (boxArr[i] == '1') {
                right++;
                operate[0] += i;
            }
        }

        for (int i = 1; i < boxArr.length; i++) {
            operate[i] = operate[i - 1] + left - right;

            if (boxArr[i] == '1') {
                left++;
                right--;
            }
        }

        return operate;
    }

}
